Generally speaking, a deadlock arises in a computer system whenever transactions require the use of more than one resource in order for the transaction to be completed. In other words, it is typical for a transaction to lock a resource so that such a transaction becomes the "owner" of that resource thereby temporarily precluding another transaction from having any access to that resource. A deadlock occurs when transactions seem to be in an infinite wait for a resource and are unable to complete.
There are three types of techniques for dealing with the deadlocks: timeout, deadlock prevention, or deadlock detection. Timeout causes all requests for resources to be denied after some specified waiting interval. It has the disadvantage that as the system becomes more congested, more and more transactions are prematurely terminated, since timeout puts an upper limit on the duration of a transaction's request. Thus, the dynamic properties of timeout make it acceptable for a lightly loaded system, but inappropriate for a congested system.
Deadlock prevention is achieved by requesting all locks at once, or by requesting locks in a specified order, or by never allowing a transaction to wait for a resource. Where deadlock prevention is employed, there is usually the tendency to lock up too many resources at one time, thereby resulting in a very slow and inefficient system.
Accordingly, various schemes have been developed to overcome the deficiencies of timeout and deadlock prevention by providing a sequence of steps for achieving deadlock detection, and initiating resolution procedures whenever deadlock occurs. Prior art techniques usually follow the steps of detecting the deadlock, picking a pending transaction to be the victim in order to break the impasse by preempting the victim from the system, backing such victim(s) out of the system in order to remove any locks on resources which are held by the victim(s), making such a released resource accessible to another pending transaction which is waiting for it, and then in some instances restarting the victim transaction.
However, prior art deadlock detection schemes have proven to be inefficient in congested systems, and have sometimes taken many hours to provide detection and resolution of deadlock situations.